/*
**    Copyright (C) 2003-2011 Institute for Systems Biology
**                            Seattle, Washington, USA.
**
**    This library is free software; you can redistribute it and/or
**    modify it under the terms of the GNU Lesser General Public
**    License as published by the Free Software Foundation; either
**    version 3 of the License, or (at your option) any later version.
**
**    This library is distributed in the hope that it will be useful,
**    but WITHOUT ANY WARRANTY; without even the implied warranty of
**    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
**    Lesser General Public License for more details.
**
**    You should have received a copy of the GNU Lesser General Public
**    License along with this library; if not, write to the Free Software
**    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
*/

package org.systemsbiology.util;

import javax.security.auth.callback.LanguageCallback;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Created by IntelliJ IDEA.
 * User: anorberg
 * Date: 5/27/11
 * Time: 5:18 PM
 * A 2-dimensional matrix of doubles, with labels of arbitrary type, with a rapid transpose operation. Both sets of
 * labels must be of the same type due to the nature of transposition. (The most common label type will be String.)
 */
public class TransposableMatrix<LR, LC> implements Iterable<Pair<LR, double[]>>{
    private LR[] rowLabels;
    private LC[] columnLabels;
    private double[][] values;

    /**
     * Constructs a TransposableMatrix.
     * @param rowLabels Array of labels for the rows in the data. Must be the same length as values.
     * @param columnLabels Array of labels for the columns in the data. Must be the same length as any element of values.
     * @param values Data. Must contain at least 1 element. If this is not rectangular, then TransposableMatrix
     *               will crash in the middle of a transpose(); careful, this is not checked for during construction.
     */
    public TransposableMatrix(LR[] rowLabels, LC[] columnLabels, double[][] values){
        this.rowLabels = rowLabels;
        this.columnLabels = columnLabels;

        this.values = values;
        if(values.length != rowLabels.length){
            throw new IllegalArgumentException("Length not matched: rowLabels vs. values");
        }
        if(values.length == 0){
            throw new IllegalArgumentException("Empty data provided to TransposableMatrix");
        }
        //cheap hack: only testing the length of 0
        if(values[0].length != columnLabels.length){
            throw new IllegalArgumentException("Length not matched: columnLabels vs. values[0]");
        }
    }

    /**
     * Returns a transposed copy of this matrix. Be careful- its labels are still bound to the labels for
     * this matrix, so modifying them will also modify the transposed copies. However, this is NOT true for
     * the data itself.
     */
    public TransposableMatrix<LC, LR> transpose(){

        double[][] result = new double[values[0].length][];
        for(int k = 0; k < result.length; ++k){
            result[k] = new double[values.length];
        }

        transposeRecursive(result, 0, values.length, 0, result.length);

        return new TransposableMatrix<LC, LR>(columnLabels, rowLabels, result);
    }

    /**
     * Returns a complete row of records from the internal representation of the matrix. If changes are
     * made to this array, those changes become part of the matrix.
     * @param row Row index to find.
     * @return The double[] representing that row of data.
     */
    public double[] getWritableRow(int row){
        if(row < 0 || row >= values.length){
            throw new IndexOutOfBoundsException(row + " is not a valid row ID");
        }
        return values[row];
    }

    /**
     * Returns the value at a specific location in the matrix.
     * @param row Row index of the value being sought.
     * @param col Column index of the value being sought.
     * @return The value at that position in the matrix.
     */
    public double get(int row, int col){
        return values[row][col]; //will throw AIOOBE in case of wrong bounds. intentional.
    }

    /**
     * The height (number of rows in) the matrix.
     * @return the number of rows in the matrix.
     */
    public int height(){
        return values.length;
    }

    /**
     * The breadth (number of columns in) the matrix.
     * @return the number of columns in the matrix.
     */
    public int breadth(){
        return values[0].length;
    }

    /**
     * Assigns a single value to a cell in the matrix.
     * @param row Row index of value to replace.
     * @param col Column index of value to replace.
     * @param value Value to overwrite previous data with at that position.
     */
    public void set(int row, int col, double value){
        values[row][col] = value;
    }

    /**
     * Assigns a new row in place of a row in the matrix. Cannot be used to extend the matrix. Outstanding
     * references to this particular row already in the matrix will be invalidated; this is a reference copy,
     * not a deep copy. New row must be the same length as the old one.
     * @param row Index of row to replace.
     * @param newValues Content of new row. Must be the same length as the old one.
     */
    public void replaceRow(int row, double[] newValues){
        if(row < 0 || row >= values.length){
            throw new IndexOutOfBoundsException(row + " not in range for rows.");
        }
        if(newValues.length != values[row].length){
            throw new IllegalArgumentException("Wrong dimension on newValues: " + newValues.length + " received, " +
                    values[row].length + " required");
        }
        values[row] = newValues;
    }

    private static final int RECURSION_LIMIT = 256;

    /**
     * Recursive inner core of transpose operation.
     * @param result Output array to write into.
     * @param rowMin Lowest row index to write.
     * @param rowMax 1 more than the highest row index to write.
     * @param colMin Lowest column index to write.
     * @param colMax 1 more than the highest column index to write.
     */
    private void transposeRecursive(double[][] result, int rowMin, int rowMax, int colMin, int colMax){
        int minSpan = rowMax - rowMin;
        int minDepth = colMax - colMin;

        //recurse? (divide-and-conquer mostly-cache-oblivious RAM-efficient transposition algorithm)
        if((minSpan > 1) && (minDepth > 1) && ((minSpan * minDepth) > RECURSION_LIMIT)){
            if(minSpan > minDepth){
                int rowHalf = (rowMin + rowMax) >> 1;
                transposeRecursive(result, rowMin, rowHalf, colMin, colMax);
                transposeRecursive(result, rowHalf, rowMax, colMin, colMax);
                return;
            } else {
                int colHalf = (colMin + colMax) >> 1;
                transposeRecursive(result, rowMin, rowMax, colMin, colHalf);
                transposeRecursive(result, rowMin, rowMax, colHalf, colMax);
                return;
            }
        }

        //base case
        for(int k = rowMin; k < rowMax; ++k){
            for(int z = colMin; z < colMax; ++z){
                result[z][k] = values[k][z];
            }
        }
    }

    /**
     * Retrieve the label for the specified row.
     * @param row Row to get a label for.
     * @return That row's label.
     */
    public LR getRowLabel(int row){
        return rowLabels[row];
    }

    /**
     * Change the label for the specified row. Be careful: if a transposition of this matrix has been built,
     * this will also alter the label of the corresponding column in the transposed matrix (or the source matrix
     * if this is a transposed matrix), because they're sharing the same object, although the data was copied.
     * @param row Row to alter.
     * @param value New label for that row.
     */
    public void setRowLabel(int row, LR value){
        rowLabels[row] = value;
    }

    /**
     * Retrieve the label for the specified column.
     * @param col Column to get a label for.
     * @return That column's label.
     */
    public LC getColumnLabel(int col){
        return columnLabels[col];
    }

    /**
     * Change the label for the specified column. Be careful: if this matrix has been part of a transpose,
     * this will also alter the label of the corresponding column in the transposed matrix.
     * @param col Column to alter.
     * @param value New label for that column.
     */
    public void setColumnLabel(int col, LC value){
        columnLabels[col] = value;
    }

    /**
     * Returns an iterator to visit each row in the matrix.
     * @return an Iterator yielding pairs of labels and the row each label applies to.
     */
    public Iterator<Pair<LR, double[]>> iterator(){
        return new RowChaser();
    }

    /**
     * Internal implementation of an Iterator to back the Iterable implementation.
     */
    private class RowChaser implements Iterator<Pair<LR, double[]>>{
        private int nextRow = 0;

        public boolean hasNext(){
            return nextRow < values.length;
        }

        public Pair<LR, double[]> next(){
            if(nextRow >= values.length){
                throw new NoSuchElementException("RowChaser ran off the end of the matrix");
            }
            return Pair.makePair(getRowLabel(nextRow), getWritableRow(nextRow++));
        }
        public void remove(){
            throw new UnsupportedOperationException("RowChaser doesn't support remove()");
        }
    }
}
